Package edu.claflin.finder.struct

Class DisjointSet<T extends Comparable<T>>

java.lang.Object
edu.claflin.finder.struct.DisjointSet<T>
public class DisjointSet<T extends Comparable<T>> extends Object
A LinkedList-based Disjoint Set data structure. Three operations combined O(m * + n* log(n)).

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private int
    length
     
    private LinkedList<T>[]
    list
     
    private int
    size
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    DisjointSet(int size)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    private boolean
    contains(T a)
    Whether the given object is in the disjoint sets.
    boolean
    disjointElements(T a, T b)
    Whether two given elements are not in the same set
    private T
    find(T x)
    Get the representative of the set the given object is in.
    void
    makeSet(T n)
    Create a new disjoint set with the given element.
    void
    merge(T a, T b)
    Merge the disjoint sets two elements are in
    int
    size()
    Get the number of disjoint sets.
    String
    toString()
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • list

      private LinkedList<T extends Comparable<T>>[] list

    • size

      private int size

    • length

      private int length

  • Constructor Details

    • DisjointSet

      public DisjointSet(int size)

  • Method Details

    • size

      public int size()
      Get the number of disjoint sets.
      Returns:
      the number of disjoint sets

    • contains

      private boolean contains(T a)
      Whether the given object is in the disjoint sets.
      Parameters:
      a - the object to determined whether it is in the disjoint sets
      Returns:
      true if the object is in the disjoint set, false otherwise

    • makeSet

      public void makeSet(T n)
      Create a new disjoint set with the given element.
      Parameters:
      n - the new element

    • find

      private T find(T x)
      Get the representative of the set the given object is in.
      Parameters:
      x - the object to find the representative of
      Returns:
      the representative

    • disjointElements

      public boolean disjointElements(T a, T b)
      Whether two given elements are not in the same set
      Parameters:
      a - the first element
      b - the second element
      Returns:
      whether the elements are not in the same set

    • merge

      public void merge(T a, T b)
      Merge the disjoint sets two elements are in
      Parameters:
      a - the first element
      b - the second element

    • toString

      public String toString()
      Overrides:
      toString in class Object